package com.leetcode;

import com.leetcode.support.Utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1238. 循环码排列 (中等)
 * 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
 * p[0] = start
 * p[i] 和 p[i+1] 的二进制表示形式只有一位不同
 * p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同
 */
public class LeetCode1238 {

    public static void main(String[] arg0) {
        int n = 2;
        int start = 3;
        System.out.println("循环码排列 = " + Arrays.toString(circularPermutation(n, start).toArray()));
        int[] res = Utils.exchangeNum(n, start);
        System.out.println("n = " + res[0] + ", start = " + res[1]);
    }

    /**
     * 与89题格雷编码完全相同，只是起始一个是0，一个是指定为start
     * n = 1  [0, 1]
     * n = 2  [00，01，11，10]
     * n = 3  [000, 001, 011, 010, 110, 111, 101, 100]
     * 每一个n都是在后面拼接, 前一个所有元素的二进制在前面拼1，然后逆序的内容，最后就是答案
     */
    public static List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        res.add(start); // 第一个数必须是start
        for (int i = 1; i <= n; i++) {
            int currSize = res.size();
            for (int j = currSize - 1; j >= 0; j--) { // 这个从大到小的循环就是在做倒序拼接
                res.add(((res.get(j) ^ start) | (1 << (i - 1))) ^ start);
            }
        }
        return res;
    }

}
